package com.tingyuge.base.arithmetic.sort;

/**
 * Created by xiaodao
 * date: 2020/4/5
 * 堆排序
 */
public class HeapSort <T extends Comparable<T>>extends Sort {

    public int heapSize;

    @Override
    protected void sort() {
        //原地建堆
        heapSize = array.length;

        for (int i = ((heapSize-1) >>1 ); i >= 0; i--) {
            siftDown(i);
        }
        while (heapSize >1){
            //交换堆顶元素和尾部元素

            swap(0,--heapSize);
            //恢复堆的位置
            siftDown(0);
        }

    }


    private void siftDown(int index) {

        //如果左孩子的索引 < 长度的话
        while (( (index << 1)+1)<heapSize ){
            int leftChildIndex = (index <<1) +1;
            // data[index] 是左右孩子的最大值
            if(leftChildIndex+1 < heapSize &&cmp (leftChildIndex+1,leftChildIndex)  > 0 ){
                leftChildIndex++;

            }
            //父元素.>=0 的话就不需要交换了
            if(cmp(index,leftChildIndex) >= 0){
                break;
            }


            swap(index,leftChildIndex);
            index = leftChildIndex;


        }
    }

}
